Devices known as routers are responsible for selecting the best path or paths to route information from one location or node within the Internet to another. For example, when information needs to be sent from a node within one network to a node within a different network, a router using a Border Gateway Protocol (“BGP”) (hereafter “BGP router”) is assigned the task of determining the best path or paths.
Because new nodes are constantly being added, deleted, etc. from networks making up the Internet, at any given point in time the best path from one node to another may change very rapidly. Realizing this, existing techniques provide BGP routers (sometimes called BGP speaker nodes) with the capability of comparing a pre-existing, best available path with a next available path formed when a change occurs to a given network. If the next available path is determined to be better than the pre-existing, best available path, then the next available path will be given the status of “best available path”. Thereafter, this new path will be used to route information in place of the pre-existing path (i.e., old, best available path).
When a new path is selected a BGP router is responsible for generating a forwarding table(s) associated with this new path. Once generated, the forwarding table is stored within the BGP router. When a packet arrives at the BGP router it is forwarded on using the stored forwarding table.
A BGP router is constantly comparing its pre-existing, stored best available path to next available paths. If a next available path is even slightly better than a pre-existing, best available path, then existing techniques require a BGP router to replace the pre-existing best available path with the new path. Thus, a given BGP router may be constantly updating its forwarding tables. Complicating matters further, each time a new, best available path is determined, it must be transmitted (referred to as “advertised”) to neighboring nodes (e.g., neighboring BGP routers). Upon receiving a new, best available path, the neighboring nodes will also update their forwarding tables. Thereafter, these neighboring nodes will advertise to their neighboring nodes and so on. Thus, any change by one BGP router has a cascading effect upon other BGP routers.
Inherent in this comparison, selection, advertisement and updating process is a time requirement. That is, relatively speaking, the comparison, selection, advertising and updating process takes up a significant amount of time. During this time it may not be possible to forward a received packet on to a next node until the process has been completed. For example, even though the comparison, selection and updating and advertising process has been completed at some nodes along a path, this process may not be completed at other nodes. As a result, any attempt to forward a packet along the path may be unsuccessful (i.e., the packet will not reach its destination) until each of the nodes along the path have completed their comparison, selection, updating and advertising process.
Other times a phenomena called “looping” occurs which results in a packet being sent back toward a preceding node instead of being forwarded on to a subsequent node.
Only when each node in the network has completed its comparison, selection and updating (and associated advertising) process can it be assured that a packet can successfully be transferred over any given path. When each node finishes this process, a network is said to have “converged.” This may take, relatively speaking, a substantial amount of time. The faster a network converges, the faster a packet can be transferred.
It is, therefore, desirable to provide for methods and devices which reduce the amount of time it takes a network to converge.